/*
深度遍历--二叉树
连接：https://leetcode.cn/problems/binary-tree-paths/description/
题目：257. 二叉树的所有路径





简介：递归解题

使⽤深度优先遍历（DFS）求解。
路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点
为叶⼦节点，将路径存储到结果中。否则，将 "->" 加⼊到路径中并递归遍历该节点的左右⼦树。
定义⼀个结果数组，进⾏递归。递归具体实现⽅法如下：
1. 如果当前节点不为空，就将当前节点的值加⼊路径 path 中，否则直接返回；
2. 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组 paths 中；
3. 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
4. 返回结果数组。
• 特别地，我们可以只使⽤⼀个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中
的当前节点移除，以回到上⼀个节点。
具体实现⽅法如下：
1. 定义⼀个结果数组和⼀个路径数组。
2. 从根节点开始递归，递归函数的参数为当前节点、结果数组和路径数组。
a. 如果当前节点为空，返回。
b. 将当前节点的值加⼊到路径数组中。
c. 如果当前节点为叶⼦节点，将路径数组中的所有元素拼接成字符串，并将该字符串存储到结果
数组中。
d. 递归遍历当前节点的左⼦树。
e. 递归遍历当前节点的右⼦树。
f. 回溯，将路径数组中的最后⼀个元素移除，以返回到上⼀个节点。
3. 返回结果数组。


*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==nullptr)
            return vector<string>();
        vector<string> vs;
        dfs(root,vs,"");
        return vs;
    }
    void dfs(TreeNode* root,vector<string>& vs,string s)
    {
        if(root->left==nullptr&&root->right==nullptr)
        {
            vs.push_back(s+to_string(root->val));
            return ;
        }
        string tmp = "";
        tmp+=to_string(root->val);
        tmp +="->";
        if(root->left)
            dfs(root->left,vs,s+tmp);
        if(root->right)
            dfs(root->right,vs,s+tmp);
       
    }
};